ITU ACM Contest 2 Solutions

Posted on 01 September, 2018 in Algorithm

Hello there,

We are going to analyze each question from ITU ACM Contest 2. You can check the questions from this link.

You can find ITU ACM Contest 1 in this link.

Question One - Bekci and His Machine Learning Experience 3 - O(N•M)

In this question. We need to do following;

1- We need to iterate through the matrix, if we encounter with the zero we mark that row and column.

2- We need to iterate through the matrix if we marked that row or column change matrix's that value with zero.

#include <cmath>
#include <cstdio>
#include <utility>
#include <vector>
#include <iostream>
#include <climits>
#include <limits>
#include <algorithm>
#include <iostream>
#include <set>
#include <fstream>
#include <queue>
#include <bitset>
#include <map>
#include <stack>

#define ll long long
using namespace std;


int main(){
    int n,m;

    scanf("%d %d", &n, &m);

    vector<vector<ll>> matrix(n, vector<ll>(m,0));

    for(int i=0;i<n;i++) for(int j=0;j<m;j++) scanf("%lld", &matrix[i][j]);

    // Mark the rows and columns vector
    vector<int> rows(n), columns(m);
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(matrix[i][j] == 0) rows[i] = 1, columns[j] = 1;

    //Change matrix[i][j] with zero, if rowVector or columnVector is one
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(rows[i] == 1 || columns[j] == 1) matrix[i][j] = 0;

    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++)
            printf("%d ", matrix[i][j]);
        printf("\n");
    }

    return 0;
}

Question Two - Yavuz and His Brilliant 3ncrypt10n Technique 2 - - O(K)

The calculations that we have done is in the following

K + K/2 + K/4 + K/8 .... ≈ 2K

Therefore, the solution runs in O(K).

For solving the question, we need to follow the instructions.

#include <vector>
#include <string>
#include <iostream>
#include <math.h>

using namespace std;


int calculator(int f, int s){ return ceil(pow(f*f*s, 1.0/3.0)); }

// This function calculates new String recursively.
int finder(vector<int> &s){
    if(s.size() == 1) return s[0];

    vector<int> newS;

    // For loop calculates the new string according to question instructions.
    for(int i=0; i<s.size()-1; i+=2) newS.push_back(calculator(s[i], s[i+1]));

    if(s.size()%2 == 1) newS.push_back( s[s.size()-1] );

    return finder(newS);
}


int main(){
    int k;
    cin >> k;

    string m;
    cin >> m;

    vector<int> inputV(k);
    for(int i=0;i<k;i++) inputV[i] = m[i];

    cout << (char)finder(inputV) << endl;



    return 0;
}

Question Three - Oğuz and His New Job 2 - O(N)

We cannot take gold from two consecutive houses. That means, if we take the gold from House[N], we can not take gold from House[N-1], House[N+1]. Therefore, we can define two variables. Those two variables represent the maximum gold that we can get from taking the house with the even or the odd index.

#include <iostream>
#include <vector>

#define ll long long

using namespace std;

int main() {
    int t,k;
    scanf("%d",&t);

    while (t-- > 0) {
        scanf("%d", &k);
        vector<ll> houses(k);

        for(auto &h: houses) scanf("%lld", &h);

        ll a=0,b=0;
        // We need to check if we can take the gold. Because it is not allowed to take gold from two consecutive houses.
        for(int i=0;i<k;i++){
            if(i%2 == 0) a = max(a+houses[i], b);
            else b = max(b+houses[i], a);
        }

        printf("%lld\n", max(a,b));
    }
    return 0;
}

Question Four - Emre vs KEO - O(N)

We do not need to find every single divisor of the number in the label. It will take too long. We just need to find if the total divisors of the label are even or not. Let's consider the following example,

Divisor Numbers

5 -> 1-5.

10 -> 1-10, 2-5.

16 -> 1-16, 2-8, 4.

As we can from the example, the number is square of another number total divisor count will be odd, otherwise, it will be even.

Since, the players are taking rocks one by one, if the total sum of rocks is even KEO will win, otherwise, Emre will win.

#include <cmath>
#include <cstdio>
#include <utility>
#include <vector>
#include <iostream>
#include <climits>
#include <limits>
#include <algorithm>
#include <iostream>
#include <set>
#include <fstream>
#include <queue>
#include <bitset>
#include <map>
#include <stack>

#define ll long long
using namespace std;

int main(){
    ll t,m,n,z,rockCounter;

    scanf("%lld", &t);

    while(t--){
        scanf("%lld",&n);
        rockCounter = 0;

        for(int i=0;i<n;i++){
            scanf("%lld", &m);

            // If the mark on the knapsack is square of some number, there will be the odd number of rocks.
            // Otherwise, there will be the even number of rocks.
            z = (ll)sqrt(m);
            rockCounter += (z*z == m);
        }

        // If there are even number of rocks in total KEO will win, Otherwise, Emre will win.
        printf((rockCounter & 1) ? "Emre\n" : "KEO\n");
    }


    return 0;
}

Question Five - Bugrul vs Prime Snake - O(N•log(N))

We need to do some calculations before moving to the solution.

1- We need to find if the number is prime or not.

2- We need to find Yalcinkaya nodes of each node. In this part, we can use Fenwick Tree or Segment Tree. I personally prefer Fenwick Tree. We need to move on the tree by using DFS. In each moving, we add one to that numbers' location.

We have found the needed information in O(N•log(N)). We can move to the solution now.

We need to move on the tree and update Bugrul's health accordingly.

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 5e5 + 55;

int N, S, res;
int bit[MAXN];
int yalcinkayas[MAXN];

bool isNotPrime[MAXN];

vector<int> graph[MAXN];

// Add and sum functions are related to Fenwick Tree.
void add(int pl, int val){
    for (int i = pl; i < MAXN; i += i & -i)
        bit[i] += val;
}

int sum(int l, int r){
    int rev = 0;

    for (int i = r; i > 0; i -= i & -i)
        rev += bit[i];

    for (int i = l - 1; i > 0; i -= i & -i)
        rev -= bit[i];

    return rev;
}

// This function finds the primes.
void findPrimes(){

    isNotPrime[1] = true;
    isNotPrime[0] = true;

    for (int i = 2; i < MAXN; i++)
        if (!isNotPrime[i])
            for (int j = i << 1; j < MAXN; j += i)
                isNotPrime[j] = true;
}

// This function finds the Yalcinkaya nodes by using Fenwick Tree.
void findYalcinkayas(int node, int previous){

    yalcinkayas[node] = sum(1, node);
    add(node + 1, 1);

    for (auto adj : graph[node])
        if (adj != previous)
            findYalcinkayas(adj, node);

    add(node + 1, -1);
}


// This is the solver function.
void dfs(int node, int previous, long long int current){
    // If the current node is prime add -1 to the Bugrul's health.
    if (!isNotPrime[node])
        current--;

    // If the current health is smaller than or equal than 0, Bugrul is dead. He can not go further.
    if (current <= 0)
        return;

    // Increment Bugrul's health.
    current += yalcinkayas[node];

    // If the current node is not prime, Bugrul enjoys from that node.
    if (isNotPrime[node])
        res++;

    for (auto adj : graph[node])
        if (adj != previous)
            dfs(adj, node, current);
}

int main(){

    findPrimes();

    scanf("%d%d", &N, &S);

    for (int a, b, i = 1; i < N; i++){
        scanf("%d%d", &a, &b);
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    findYalcinkayas(S, 0);
    dfs(S, 0, 1);

    printf("%d\n", res);
    return 0;
}

Special thanks to Burak Bugrul for the implementation of this question.

algorithm contest Segment Tree DFS Math ITU ACM